package offer.zixing.chapter15;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Test106 {

    public static void main(String[] args) {
        int[][] graph = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
        // 邻接表，图中每个节点创建一个容器
        int[][] graph2 = {{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}};
        System.out.println(isBipartite(graph));
    }

    // 类似与红黑树，给节点染色，遍历整个图节点，将该节点染为【红色】，相连的节点染为【黑色】，没有遍历的无色
    public static boolean isBipartite(int[][] graph) {
        // 图中有 size 个节点
        int size = graph.length;
        // 预置每个节点不染色，即 -1
        int[] colors = new int[size];
        Arrays.fill(colors, -1);
        // 遍历给每个节点都染色
        for (int i = 0; i < size; i++) {
            // 如果当前节点已经染色则跳过
            if (colors[i] == -1) {
                // 给当前节点染色为 0
                if (!setColor(graph, colors, i, 0)) {
                    return false;
                }
            }
        }
        return true;
    }

    // 广度搜索给节点染色
    private static boolean setColor(int[][] graph, int[] colors, int i, int color) {
        // 初始化一个队列
        Queue<Integer> queue = new LinkedList<>();
        queue.add(i);
        // 给当前节点染色为 【红色】
        colors[i] = color;
        while (!queue.isEmpty()) {
            int v = queue.poll();
            // 遍历当前节点相连接的节点
            for (int neighbor : graph[v]) {
                // 如果当前节点已经染色
                if (colors[neighbor] >= 0) {
                    // 且和当前节点颜色一致，说明不是二分图，结束
                    if (colors[neighbor] == colors[v]) {
                        return false;
                    }
                }
                // 没有染色，则添加到队列
                else {
                    queue.add(neighbor);
                    // 染色为【黑色】
                    colors[neighbor] = 1 - colors[v];
                }
            }
        }
        return true;
    }


    private static boolean setColor2(int[][] graph, int[] colors, int i, int color) {
        if (colors[i] >= 0) {
            return colors[i] == color;
        }
        colors[i] = color;
        for (int neighbor : graph[i]) {
            if (!setColor2(graph, colors, neighbor, 1 - color)) {
                return false;
            }
        }
        return true;
    }
}
